1185D - Extra Element - CodeForces Solution

from collections import defaultdict


n = int(input())
nums = [int(x) for x in input().strip().split()]

idx = defaultdict(list)
for i, x in enumerate(nums):
    idx[x].append(i + 1)


nums.sort()
deltas = defaultdict(int)
for i in range(n - 1):
    deltas[nums[i+1] - nums[i]] += 1



if len(deltas) == 1:
    true_idx = idx[nums[0]][0]
    print(true_idx)
    exit()
    
if len(deltas) >= 4:
    print(-1)
    exit()



if len(deltas) == 2 and deltas[nums[1] - nums[0]] == 1:
    true_idx = idx[nums[0]][0]
    print(true_idx)
    exit()
    
if len(deltas) == 2 and deltas[nums[n - 1] - nums[n - 2]] == 1:
    true_idx = idx[nums[-1]][0]
    print(true_idx)
    exit()


for i in range(1, n - 1):
    d1 = nums[i] - nums[i - 1]
    d2 = nums[i + 1] - nums[i]
    new_d = d1 + d2
    deltas[d1] -= 1
    if deltas[d1] == 0:
        deltas.pop(d1)
    deltas[d2] -= 1
    if deltas[d2] == 0:
        deltas.pop(d2)
    deltas[new_d] += 1
    
            
    if len(deltas) == 1:
        true_idx = idx[nums[i]][0]
        print(true_idx)
        exit()
        deltas[new_d] -= 1
    if deltas[new_d] == 0:
        deltas.pop(new_d)
    deltas[d1] += 1
    deltas[d2] += 1

print(-1)